// eee.Sheffield.PZ.Imaging
//
// Copyright ?Ping Zou, 2007
// sg71.cherub@gmail.com

using System;
using System.Collections.Generic;
using System.Text;
using eee.Sheffield.PZ.Math;
using System.Drawing;
using System.Drawing.Imaging;

namespace eee.Sheffield.PZ.Imaging.ImageFilter
{
    public class LineSegmentSplitter : ImageFilter//, IGraylevelImageFilter
    {
        #region Fields
        private List<PZPoint> _tripleJunctionList;  // triple junction list
        private List<PZPoint> _freeEndList;  // free end points list
        private List<LineSegment> _lineSegmentList; // line segment list
        #endregion

        #region Properties
        public List<PZPoint> FreeEndList { get { return _freeEndList; } }
        public List<PZPoint> TripleJunctionList { get { return _tripleJunctionList; } }
        public List<LineSegment> LineSegmentList { get { return _lineSegmentList; } }
        #endregion

        #region Constructor
        public LineSegmentSplitter(List<PZPoint> freeEndList, List<PZPoint> tripleJunctionList)
        {
            _tripleJunctionList = new List<PZPoint>(tripleJunctionList);
            _freeEndList = new List<PZPoint>(freeEndList);
            _flag = "[Image -> Morphology -> Line Segment Splitter]";
        }
        #endregion

        #region Apply filter
        protected override PZMath_matrix ApplyDoubleGraylevelImageFilter(PZMath_matrix srcMatrix, out string logText)
        {
            int freeEnd = _freeEndList.Count;
            int junction = _tripleJunctionList.Count;

            PZMath_matrix dstMatrix = new PZMath_matrix(srcMatrix);
            bool[,] dstBoolMatrix = dstMatrix.ConvertToBoolMatrix(125);
            _lineSegmentList = new List<LineSegment>(0);

            // start tracing line segment from end points
            while (_freeEndList.Count > 0)
                // for each end point
            {
                PZPoint currentPoint = (PZPoint)_freeEndList[0];
                _freeEndList.RemoveAt(0);   // remove end point from end point list  
                
                LineSegment lineSegment = new LineSegment();
                // add current point in line segment as "end point"
                lineSegment.AddEndPoint(new PZPoint(currentPoint));
                // remove current point from dstMatrix
                dstBoolMatrix[(int)currentPoint.x, (int)currentPoint.y] = false;
                
                // trace single line segment
                TraceSingleLineSegment(ref lineSegment, ref currentPoint, ref dstBoolMatrix, ref _freeEndList, ref _tripleJunctionList);
               
                _lineSegmentList.Add(lineSegment);
            }; // while(_freeEndList.Count > 0)

            //Bitmap afterTracingFreeEnds = ConvertBitmapMatrix.ToBitmap(dstBoolMatrix);
            //afterTracingFreeEnds.Save("after tracing free ends.bmp", ImageFormat.Bmp);

            // start tracing line segments from junction points
            // firstly, trace only 4-neighbours of all the junction points
            foreach (PZPoint junctionPoint in _tripleJunctionList)
            {
                //if (junctionPoint.EqualTo(new PZPoint(80, 454)))
                //{
                //    Bitmap currentGraph = ConvertBitmapMatrix.ToBitmap(dstBoolMatrix);
                //    currentGraph.Save("current graph.bmp", ImageFormat.Bmp);
                //    Console.ReadLine();
                //}
                RemoveFromDstMatrix(ref dstBoolMatrix, junctionPoint);

                List<PZPoint> fourNeighbourList = Search4Neighbours(dstBoolMatrix, junctionPoint);
                int index = 0;
                while (index < fourNeighbourList.Count)
                //while (fourNeighbourList.Count > 0)
                {
                    //PZPoint neighbour = fourNeighbourList[0];
                    PZPoint neighbour = fourNeighbourList[index];

                    // remove the other neighbours from dst matrix
                    for (int i = 0; i < fourNeighbourList.Count; i++)
                    {
                        if (i == index)
                            continue;
                        RemoveFromDstMatrix(ref dstBoolMatrix, (PZPoint)fourNeighbourList[i]);
                    }
                    //for (int i = 1; i < fourNeighbourList.Count; i++)
                    //    RemoveFromDstMatrix(ref dstBoolMatrix, (PZPoint)fourNeighbourList[i]);
                    

                    LineSegment lineSegment = new LineSegment();
                    lineSegment.AddEndPoint(new PZPoint(junctionPoint));
                    
                    PZPoint currentPoint = neighbour;                    

                    // current point could be a junction point or a line segment point
                    if (!IsInTripleJunctionList(currentPoint, _tripleJunctionList))
                    // current is a line segment point
                    {
                        lineSegment.AddPoint(new PZPoint(currentPoint));
                        dstBoolMatrix[(int)currentPoint.x, (int)currentPoint.y] = false;
                        TraceSingleLineSegment(ref lineSegment, ref currentPoint, ref dstBoolMatrix, ref _freeEndList, ref _tripleJunctionList);
                        _lineSegmentList.Add(lineSegment);
                    }

                    // add the other neighbours to dst matrix
                    for (int i = 0; i < fourNeighbourList.Count; i++)
                    {
                        if (i == index)
                            continue;
                        AddToDstMatrix(ref dstBoolMatrix, (PZPoint)fourNeighbourList[i]);
                    }
                    //for (int i = 1; i < fourNeighbourList.Count; i++)
                    //    AddToDstMatrix(ref dstBoolMatrix, (PZPoint)fourNeighbourList[i]);

                    //fourNeighbourList.RemoveAt(0);
                    index++;
                } // while (fourNeighbourList.Count > 0)

                // remove all non-junctin four diagonal neighbours from dst bool matrix
                foreach (PZPoint neighbour in fourNeighbourList)
                {
                    if (!IsInTripleJunctionList(neighbour, _tripleJunctionList))
                        RemoveFromDstMatrix(ref dstBoolMatrix, neighbour);
                }

                AddToDstMatrix(ref dstBoolMatrix, junctionPoint);
            } // foreach _tripleJunctionList

            // secondly, trace only 4-diagonal-neighbours of all the junction points
            foreach (PZPoint junctionPoint in _tripleJunctionList)
            {
                RemoveFromDstMatrix(ref dstBoolMatrix, junctionPoint);
                
                List<PZPoint> fourDiagonalNeighbourList = SearchDiagonal4Neighbours(dstBoolMatrix, junctionPoint);
                int index = 0;
                while(index < fourDiagonalNeighbourList.Count)
                //while(fourDiagonalNeighbourList.Count > 0)
                {
                    //PZPoint neighbour = (PZPoint)fourDiagonalNeighbourList[0];
                    PZPoint neighbour = (PZPoint)fourDiagonalNeighbourList[index];

                    // remove the other neighbours from the dst matrix
                    for (int i = 0; i < fourDiagonalNeighbourList.Count; i++)
                    {
                        if (i == index)
                            continue;
                        RemoveFromDstMatrix(ref dstBoolMatrix, (PZPoint)fourDiagonalNeighbourList[i]);
                    }
                    //for (int i = 1; i < fourDiagonalNeighbourList.Count; i++)
                    //    RemoveFromDstMatrix(ref dstBoolMatrix, (PZPoint)fourDiagonalNeighbourList[i]);

                    LineSegment lineSegment = new LineSegment();
                    lineSegment.AddEndPoint(new PZPoint(junctionPoint));

                    PZPoint currentPoint = neighbour;

                    // current point could be a junction point or a line segment point
                    if (!IsInTripleJunctionList(currentPoint, _tripleJunctionList))
                    // current is a line segment point
                    {
                        lineSegment.AddPoint(new PZPoint(currentPoint));
                        dstBoolMatrix[(int)currentPoint.x, (int)currentPoint.y] = false;
                        TraceSingleLineSegment(ref lineSegment, ref currentPoint, ref dstBoolMatrix, ref _freeEndList, ref _tripleJunctionList);
                        _lineSegmentList.Add(lineSegment);
                    }

                    // add the other neighbours to the dst matrix
                    for (int i = 0; i < fourDiagonalNeighbourList.Count; i++)
                    {
                        if (i == index)
                            continue;
                        AddToDstMatrix(ref dstBoolMatrix, (PZPoint)fourDiagonalNeighbourList[i]);
                    }

                    index++;
                    //for (int i = 1; i < fourDiagonalNeighbourList.Count; i++)
                    //    AddToDstMatrix(ref dstBoolMatrix, (PZPoint)fourDiagonalNeighbourList[i]);

                    //fourDiagonalNeighbourList.RemoveAt(0);
                } // while(fourDiagonalNeighbourList.Count > 0)

                // remove all non-junctin four diagonal neighbours from dst bool matrix
                foreach (PZPoint neighbour in fourDiagonalNeighbourList)
                {
                    if (!IsInTripleJunctionList(neighbour, _tripleJunctionList))
                        RemoveFromDstMatrix(ref dstBoolMatrix, neighbour);
                }

                AddToDstMatrix(ref dstBoolMatrix, junctionPoint);
            }

            // thirdly, connect the contiguous junction points  
            foreach (PZPoint junctionPoint in _tripleJunctionList)            
            {                                
                List<PZPoint> neighbourList = Search8Neighbours(dstBoolMatrix, junctionPoint);
                if (neighbourList.Count == 0)
                    RemoveFromDstMatrix(ref dstBoolMatrix, junctionPoint);
                else
                {
                    foreach (PZPoint endPoint in neighbourList)
                    {
                        LineSegment lineSegment = new LineSegment();
                        lineSegment.AddEndPoint(new PZPoint(junctionPoint));
                        lineSegment.AddEndPoint(new PZPoint(endPoint));
                        _lineSegmentList.Add(lineSegment);
                    }
                    RemoveFromDstMatrix(ref dstBoolMatrix, junctionPoint);
                }                               
            }

            //remove "end loop"
            RemoveInvalidLineSegment(_lineSegmentList);

            logText = "succeed. ";
            dstMatrix = new PZMath_matrix(dstBoolMatrix);
            return dstMatrix;
        } // ApplyDoubleGraylevelImageFilter()

        protected override PZMath_matrix[] ApplyDoubleColourImageFilter(PZMath_matrix[] srcMatrixArray, out string logText)
        {
            // TODO: add this function
            throw new Exception("The method or operation is not implemented.");
        } // ApplyDoubleColourImageFilter()
        #endregion

        #region search neighbour method
        /// <summary>
        /// search 8 neighbours, return neighbours
        /// </summary>
        /// <param name="row"></param>
        /// <param name="col"></param>
        /// <returns></returns>
        private List<PZPoint> Search8Neighbours(bool[,] binaryImg, PZPoint p)
        {
            // image(matrix) info
            int width = binaryImg.GetLength(0);
            int height = binaryImg.GetLength(1);

            List<PZPoint> neighbours = new List<PZPoint>(0);

            int x = (int)p.x;
            int y = (int)p.y;

            if (x - 1 >= 0 && y - 1 >= 0)
                if (binaryImg[x - 1, y - 1])
                    neighbours.Add(new PZPoint(x - 1, y - 1));
            if (x - 1 >= 0)
                if (binaryImg[x - 1, y])
                    neighbours.Add(new PZPoint(x - 1, y));
            if (x - 1 >= 0 && y + 1 < height)
                if (binaryImg[x - 1, y + 1])
                    neighbours.Add(new PZPoint(x - 1, y + 1));
            if (y - 1 >= 0)
                if (binaryImg[x, y - 1])
                    neighbours.Add(new PZPoint(x, y - 1));
            if (y + 1 < height)
                if (binaryImg[x, y + 1])
                    neighbours.Add(new PZPoint(x, y + 1));
            if (x + 1 < width && y - 1 >= 0)
                if (binaryImg[x + 1, y - 1])
                    neighbours.Add(new PZPoint(x + 1, y - 1));
            if (x + 1 < width)
                if (binaryImg[x + 1, y])
                    neighbours.Add(new PZPoint(x + 1, y));
            if (x + 1 < width && y + 1 < height)
                if (binaryImg[x + 1, y + 1])
                    neighbours.Add(new PZPoint(x + 1, y + 1));

            return neighbours;
        } // Search8Neighbours()

        /// <summary>
        /// search 4 neighbours, return neighbours
        /// </summary>
        /// <param name="binaryImg"></param>
        /// <param name="p"></param>
        /// <returns></returns>
        private List<PZPoint> Search4Neighbours(bool[,] binaryImg, PZPoint p)
        {
            int width = binaryImg.GetLength(0);
            int height = binaryImg.GetLength(1);

            List<PZPoint> neighbours = new List<PZPoint>(0);
            int x = (int)p.x;
            int y = (int)p.y;
            if (x - 1 >= 0)
                if (binaryImg[x - 1, y])
                    neighbours.Add(new PZPoint(x - 1, y));
            if (y - 1 >= 0)
                if (binaryImg[x, y - 1])
                    neighbours.Add(new PZPoint(x, y - 1));
            if (y + 1 < height)
                if (binaryImg[x, y + 1])
                    neighbours.Add(new PZPoint(x, y + 1));
            if (x + 1 < width)
                if (binaryImg[x + 1, y])
                    neighbours.Add(new PZPoint(x + 1, y));
            return neighbours;
        } // Search4Neighbours()

        /// <summary>
        /// search diagonal 4 neighbour
        /// </summary>
        /// <param name="binaryImg"></param>
        /// <param name="p"></param>
        /// <returns></returns>
        private List<PZPoint> SearchDiagonal4Neighbours(bool[,] binaryImg, PZPoint p)
        {
            int width = binaryImg.GetLength(0);
            int height = binaryImg.GetLength(1);
            List<PZPoint> neighbours = new List<PZPoint>();
            int x = (int)p.x;
            int y = (int)p.y;
            if (x - 1 >= 0 && y - 1 >= 0)
                if (binaryImg[x - 1, y - 1])
                    neighbours.Add(new PZPoint(x - 1, y - 1));
            if (x - 1 >= 0 && y + 1 < height)
                if (binaryImg[x - 1, y + 1])
                    neighbours.Add(new PZPoint(x - 1, y + 1));
            if (x + 1 < width && y - 1 >= 0)
                if (binaryImg[x + 1, y - 1])
                    neighbours.Add(new PZPoint(x + 1, y - 1));
            if (x + 1 < width && y + 1 < height)
                if (binaryImg[x + 1, y + 1])
                    neighbours.Add(new PZPoint(x + 1, y + 1));
            return neighbours;
        } // SearchDiagonal4Neighbours()

        #endregion

        #region searc list method
        private bool IsInFreeEndList(PZPoint p, List<PZPoint> freeEndList)
        {
            bool isInFreeEndList = false;
            foreach (PZPoint q in freeEndList)
            {
                if (q.EqualTo(p))
                {
                    isInFreeEndList = true;
                    break;
                }
            }

            return isInFreeEndList;
        } // IsInFreeEndList()

        private bool IsInTripleJunctionList(PZPoint p, List<PZPoint> tripleJunctionList)
        {
            bool isInTripleJunctionList = false;
            foreach (PZPoint q in tripleJunctionList)
            {
                if (q.EqualTo(p))
                {
                    isInTripleJunctionList = true;
                    break;
                }
            }

            return isInTripleJunctionList;
        } // IsInTripleJunctionList()
        #endregion

        #region trace single line segment method
        /// <summary>
        /// trace a single line segment, started from current point
        /// current point has been added to the line segment
        /// current point has been removed from dst matrix
        /// </summary>
        /// <param name="lineSegment"></param>
        /// <param name="currentPoint"></param>
        /// <param name="dstBoolMatrix"></param>
        private void TraceSingleLineSegment(ref LineSegment lineSegment, ref PZPoint currentPoint, ref bool[,] dstBoolMatrix,
            ref List<PZPoint> freeEndList, ref List<PZPoint> tripleJunctionList)
        {
            while (true)
            // trace a line segment
            {
                // search 8 neighbours
                List<PZPoint> eightNeighbourList = Search8Neighbours(dstBoolMatrix, currentPoint);
                if (eightNeighbourList.Count == 0)
                    // this scenario happens if a line segment is only 2 pixels in length
                    // current is a free end.
                {
                    lineSegment.AddEndPoint(new PZPoint(currentPoint));
                    freeEndList.Remove(currentPoint);
                    RemoveFromDstMatrix(ref dstBoolMatrix, currentPoint);
                    break;
                }
                if (eightNeighbourList.Count > 1)
                // more than one 8 neighbours
                {
                    // search 4 neighbours
                    List<PZPoint> fourNeighbourList = Search4Neighbours(dstBoolMatrix, currentPoint);

                    if (fourNeighbourList.Count > 1)                                            
                        throw new ApplicationException("LineSegmentSplitter::ApplyDoubleGraylevelImageFilter(), current point is not a junction point but detected more than one 4 neighbours.");

                    PZPoint fourNeighbour = (PZPoint)fourNeighbourList[0];

                    if (IsInTripleJunctionList(fourNeighbour, tripleJunctionList))
                    // the four neighbour is a junction point
                    // close line segment at the junction point
                    // stop tracing
                    {
                        lineSegment.AddEndPoint(new PZPoint(fourNeighbour));
                        break;
                    }
                    else if (!(IsInFreeEndList(fourNeighbour, freeEndList)))
                    // the four neighbour is a line segment point
                    // add four neighbour to line segment
                    // set four neighbour the current point
                    // remove four neighbour from dst matrix
                    {
                        lineSegment.AddPoint(new PZPoint(fourNeighbour));
                        RemoveFromDstMatrix(ref dstBoolMatrix, fourNeighbour);
                        //dstBoolMatrix[(int)fourNeighbour.x, (int)fourNeighbour.y] = false;
                        currentPoint = fourNeighbour;
                    }
                }
                else
                // only one neighbours
                {
                    PZPoint neighbour = (PZPoint)eightNeighbourList[0];
                    if (IsInFreeEndList(neighbour, freeEndList))
                    // next neighbour is an end point
                    // close line segment at next neighbour
                    // remove the end point from end point list
                    // remove the end point from dstMatrix
                    // stop tracing
                    {
                        lineSegment.AddEndPoint(new PZPoint(neighbour));
                        freeEndList.Remove(neighbour);
                        RemoveFromDstMatrix(ref dstBoolMatrix, neighbour);
                        //dstBoolMatrix[(int)neighbour.x, (int)neighbour.y] = false;
                        break;
                    }
                    else if (IsInTripleJunctionList(neighbour, tripleJunctionList))
                    // next neighbour is a junction point
                    // close line segment at next neighbour                        
                    // stop tracing
                    {
                        lineSegment.AddEndPoint(new PZPoint(neighbour));
                        break;
                    }
                    else
                    // next neighbour is a line segment point
                    // add neighbour to line segment
                    // remove neighbour from dstMatrix
                    // set neighbour as current point
                    {
                        lineSegment.AddPoint(new PZPoint(neighbour));
                        RemoveFromDstMatrix(ref dstBoolMatrix, neighbour);
                        //dstBoolMatrix[(int)neighbour.x, (int)neighbour.y] = false;
                        currentPoint = neighbour;
                    }
                }
            };  // while(true)
        } // TraceSingleLineSegment()
        
        private void RemoveFromDstMatrix(ref bool[,] dstBoolMatrix, PZPoint p)
        {
            dstBoolMatrix[(int)p.x, (int)p.y] = false;
        } // RemoveFromDstMatrix()

        private void AddToDstMatrix(ref bool[,] dstBoolMatrix, PZPoint p)
        {
            dstBoolMatrix[(int)p.x, (int)p.y] = true;
        } // AddToDstMatrix()
        #endregion

        #region utility method
        /// <summary>
        /// remove "invalid" line segment
        /// </summary>
        /// <param name="lineSegmentList"></param>
        private void RemoveInvalidLineSegment(List<LineSegment> lineSegmentList)
        {
            int count = lineSegmentList.Count;
            int index = 0;
            bool removed;
            while (index < count)
            {
                removed = false;
                LineSegment l = (LineSegment)lineSegmentList[index];
                int length = l.PointList.Count;
                l.InitializePriorModel();
                for (int i = 0; i < length; i++)
                {
                    if (double.IsNaN(((PZDirection)l.DirectionList[i]).x))
                    {
                        lineSegmentList.RemoveAt(index);
                        count--;
                        removed = true;
                        break;
                    }
                }
                if (!removed)
                    index++;
            }
        } // RemoveInvalidLineSegment()
        #endregion

        #region I/O method
        /// <summary>
        /// return line segments image
        /// </summary>
        /// <param name="srcImage"></param>
        /// <returns></returns>
        public Bitmap LineSegmentImage(Bitmap srcImage)
        {
            LineSegmentConfiguration lineSegmentConfiguration = new LineSegmentConfiguration(_lineSegmentList);
            Bitmap dstImage = lineSegmentConfiguration.DrawLineSegments(srcImage);
            return dstImage;
        } // LineSegmentImage()
        #endregion
    }
}
